This invention relates to local area networks in which computers communicate with one another over a transmission medium, and more particularly to a system for avoiding collision on a wireless transmission medium between stations.
In a local area network (LAN), a collision occurs when multiple units simultaneously attempt to access the communication channel. The communication channel is the medium through which the data carrier propagates. In a wireless network, the channel medium is free space and the data carrier comprises modulated infrared radiation. It is difficult to detect a collision between multiple units attempting to grab a wireless channel because of the inability to resolve a faint distant signal (e.g. emitted from a remote station) which is superimposed on an extremely strong local signal (e.g. emitted by a competing station).
In wired networks, a protocol known as Carrier Sense Multiple Access with Collision Detection (CSMA/CD) is utilized to detect collisions on the channel. Detection of a collision causes appropriate back-off algorithms to be executed. In a CSMA/CD based system, a station wishing to transmit a message listens until the transmission channel is idle before commencing to transmit an information packet. The station continues to listen to the channel after starting a transmission, and if a collision is detected, i.e. more than one station has commenced transmitting a data packet, the station which has detected the collision terminates its message transmission and transmits a jam pattern. The jam pattern informs all the other stations of the collision and they start executing their own back-off algorithms. The back-off algorithm includes terminating message transmission and waiting a random time before attempting to commence another message transmission.
The CSMA/CD protocol is used primarily in wired LAN. The CSMA/CD protocol is generally unsuitable for a wireless LAN comprising a single wireless channel because transmission and reception of signals cannot take place on the single channel, that is, a station cannot generally receive while it is transmitting because the dynamic range is too large. As a result the focus in wireless LANs has been on collision avoidance as opposed to collision detection. Various methods or protocols for Medium Access Control (MAC) have been developed to avoid collisions between units accessing the wireless communication channels. Such methods comprise a communication reservation protocol in which units, i.e. stations, coupled to the wireless LAN must first establish a connection with a peer station via the MAC level control frames prior to the actual data transfer. In such systems, the integrity of the negotiating control frames are very important to the effective operation of the network.
One widely used protocol for wireless LAN communication is known as CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance). The CSMA/CA method attempts to minimize the likelihood of collisions between competing stations. According to the CSMA/CA protocol, access to the communication channel by multiple units is controlled by each unit""s ability to detect channel activity, i.e. carrier sense, and to implement algorithms to minimize the likelihood of simultaneous access, i.e. collision avoidance. The effective operation of a network utilizing CSMA/CA depends on the integrity of the negotiating control frames. According to this known method, a reservation comprises a six packet structure, and software utilizing a Medium Access Control (MAC) layer oversees a reservation on the channel. A station wishing to transmit a data packet first broadcasts a Connect Request (CR) packet to all the stations coupled to the LAN. The CR packet includes an identification field for the originator of the reservation request and a destination field identifying the station with which the reservation is being sought. In response, the destination station broadcasts a Connect Confirm (CC) packet. The broadcast of the CC packet confirms the establishment of a reservation on the communication channel between the originator and the destination station. The originating station then transmits a data transfer (XFR) packet for the reservation. The XFR packet includes the data to be transferred and typically comprises the largest packet in the six reservation packet structure. The XFR data packet is addressed specifically to the destination station. Upon receipt of the XFR data packet, the destination station responds with a Data Transfer Acknowledge (XACK) packet to confirm reception of the data packet. The XACK packet is specifically addressed to the originator station. In response to the XACK packet, the originator station broadcasts a Disconnect Request (DR) packet which is directed to the destination station and also received by the other stations. The DR packet indicates the intention of the originating station to terminate the reservation of the communication channel. The destination station broadcasts a Disconnect Confirm (DC) packet which is directed to the originating station and also received by the other stations. Other stations which have been waiting for the communication channel to become free can now initiate their procedures (i.e. Connect Request) to gain access to the channel and establish a reservation.
Problems remain with the CSMA/CA protocol applied to wireless LANs. When a Connect Request (CR) packet is sent by a station, no other stations should attempt to transmit another Connect Request (CR) packet until the reservation awarded to the station sending the first Connect Request (CR) packet is completed and the channel is made available to the remaining stations. This means that the MAC layer software must closely monitor the status of the receiver to determine if a Connect Request (CR) packet has been sent by another station prior to sending its own CR packet. An inherent problem with this approach is that time spent executing the decision making process results in windows where the desired state could be missed and reservations corrupted by back-to-back Connect Request (CR) packets being sent by competing stations. Furthermore, the transmission of Connect Request (CR) packets by multiple stations increases the likelihood of collisions in the communication channel and confuses stations vying for the channel as to which station established the reservation. When this confusion occurs, the stations must execute back-off procedures which tend to be long and complicated. The added overhead to process and handle back-to-back Connect Request (CR) packets also impairs the throughput and efficiency of CSMA/CA based systems. A further problem with such systems arises from the fact that the execution time of the reservation protocol becomes the controlling factor to the window of error, and thus the window of error will vary based on the speed of the system CPU, i.e. microprocessor. This means that a station""s susceptibility will depend in part on the speed of the microprocessor used for the system CPU.
The present invention overcomes these disadvantages by providing a system wherein software control initiates packet transmission and logic controls the entry of packets into the communication channel. The logic includes the capability to issue unconditional aborts to avoid collisions during packet transmit procedures and off-load time critical processing functions associated with the reservation protocol. The system according to the present invention provides a substantial improvement in network performance based on its ability to rigidly control entry into the communication channel of critical MAC control packets.
The present invention provides a Carrier Sense Multiple Access with Automatic Abort collision avoidance (CSMA/AA) controller suitable for application in a wireless Local Area Network (LAN).
The CSMA/AA controller according to the present invention achieves an improvement in wireless network operation over that obtained using a conventional CSMA/CA implementation. The implementation according to the present invention reduces the number of invalid states in the MAC sub-layer which account for a large quantity of idle time periods resulting from the execution of time consuming back-off procedures.
A feature of the CSMA/AA controller is hardware logic control for time critical functions. The hardware logic provides a means to detect events and fault conditions under the CSMA reservation protocol which may otherwise be missed by the Medium Access Control software leading to collisions on the channel. This aspect of the present invention also allows the off-loading of time critical functions from the system CPU, which in turn, reduces variability arising from system overhead execution requirements and processor speed.
In a first aspect the present invention provides a local area network LAN station for use with a transceiver coupled to a communication channel for operating on the LAN, the transceiver providing receive data and transmit data ports for the station, said station comprising: (a) communication controller means coupled to said transceiver to control transmission and reception of data on said communication channel; (b) memory means for storing data to be transmitted and data to be received on said communication channel; (c) said communication controller means including receiver means coupled to the receive port of said transceiver for receiving data from said communication channel; (d) said communication controller means having transmitter means coupled to the transmit port of said transceiver for transmitting data on said communication channel; (e) said communication controller means including logic means to abort a transmission procedure when a data reception is pending; (f) said logic means being coupled to said receiver means and having means responsive to activity on said receive port for generating an abort control signal for aborting operation of said transmitter means when receive activity is detected.
In another aspect, the present invention provides a method for avoiding collision between stations communicating over a single communication channel coupled by a local area network LAN, each station including a transceiver for operating on the communication channel and receiver means for receiving data from the transceiver and transmitter means for transmitting data to the transceiver and controller means for controlling the transfer of data between the station and the communication channel and logic circuit means, said method comprising the steps of: (a) determining if said communication channel is available; (b) initiating a data transmission by generating a signal through said controller means for enabling the transmitter means when said communication channel is available from step (a); (c) enabling said logic circuit means through said controller means; (d) commencing transmission of data on said communication channel through said transceiver and transmitter means; (e) monitoring receive data activity in said receiver means using said logic circuit means; (f) aborting operation of said transmitter means by generating an abort signal through said logic circuit means in response to the detection of receive data activity; and (f) notifying said controller means of the aborted transmission.